import heapq


class Solution:
    def minimumEffortPath(self, heights: list) -> int:
        adj = {}
        for i in range(len(heights)):
            for j in range(len(heights[i])):
                if (i, j) not in adj:
                    adj[(i, j)] = []
                for m, n in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    if i + m < 0 or i + m >= len(heights):
                        continue
                    if j + n < 0 or j + n >= len(heights[i]):
                        continue
                    absVal = abs(heights[i][j] - heights[i + m][j + n])
                    adj[(i, j)] += [(absVal, (i + m, j + n))]
        queue = [(0, (0, 0))]
        res = 0
        visited = set()
        while queue:
            absVal, node = heapq.heappop(queue)
            visited.add(node)
            res = max(res, absVal)
            if node == (len(heights) - 1, len(heights[-1]) - 1):
                break
            for ele in adj[node]:
                if ele[1] in visited:
                    continue
                heapq.heappush(queue, ele)

        return res


if __name__ == "__main__":
    print(Solution().minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]]))
